//: [Previous](@previous)

/*:
                     1
                  /    \
                 2       3
               /   \    /  \
              4     5  6    7
            /            \
           8               9
 
 前序遍历：1 2 4 8 5 3 6 9 7
 
 中序遍历：8 4 2 5 1 6 9 3 7
 
 后序遍历：8 4 5 2 9 6 7 3 1
 
 层次遍历：1 2 3 4 5 6 7 8 9
 */

let root = TreeNode(1)
let rootL = TreeNode(2)
let rootR = TreeNode(3)
root.left = rootL
root.right = rootR
let rootLL = TreeNode(4)
let rootLR = TreeNode(5)
rootL.left = rootLL
rootL.right = rootLR
let rootLLL = TreeNode(8)
rootLL.left = rootLLL
let rootRL = TreeNode(6)
let rootRR = TreeNode(7)
rootR.left = rootRL
rootR.right = rootRR
let rootRLR = TreeNode(9)
rootRL.right = rootRLR
/*:
 ### 144. Binary Tree Preorder Traversal 二叉树的前序遍历
 Given a binary tree, return the preorder traversal of its nodes' values.
 给定一个二叉树，返回它的 前序 遍历。
 ```
 Example:
 Input: [1,null,2,3]
 1
   \
     2
   /
  3
 Output: [1,2,3]
 ```
 Follow up: Recursive solution is trivial, could you do it iteratively?
 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
*/
class Solution {
    /// 1. 使用递归算法 - 性能差 - 每次 preorderTraversal() 都会重复调用很多次
    class func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        result.append(root.val)
        result += preorderTraversal(root.left)
        result += preorderTraversal(root.right)
        return result
    }
    /// 2. 使用迭代算法
    /// 使用辅助栈来进行
    class func preorderTraversal2(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        var tree: [TreeNode] = []
        tree.append(root)
        
        while !tree.isEmpty {
            
            let node = tree.popLast()!
            result.append(node.val)
            
            if node.right != nil {
                tree.append(node.right!)
            }
            
            if node.left != nil {
                tree.append(node.left!)
            }
        }
        
        return result
    }
    
    /// 3. 使用迭代算法 + 辅助节点
    ///
    class func preorderTraversal3(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        
        var p: TreeNode? = root
        var tree: [TreeNode] = []
        
        while !tree.isEmpty || p != nil {
            if p != nil {
                tree.append(p!)
                result.append(p!.val)
                p = p?.left
            } else {
                let node = tree.popLast()!
                p = node.right
            }
        }
        return result
    }
}
print("前序")
print(Solution.preorderTraversal(root))
print(Solution.preorderTraversal2(root))
print(Solution.preorderTraversal3(root))
/*:
 ### 94. Binary Tree Inorder Traversal
 Given a binary tree, return the inorder traversal of its nodes' values.
 给定一个二叉树，返回它的 中序 遍历。
 ```
 Input: [1,null,2,3]
 1
   \
    2
   /
 3
 Output: [1,3,2]
 ```
 Follow up: Recursive solution is trivial, could you do it iteratively?
 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
class Solution2 {
    /// 1.递归
    class func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        result += inorderTraversal(root.left)
        result.append(root.val)
        result += inorderTraversal(root.right)
        return result
    }
    /// 2. 借助栈的迭代
    class func inorderTraversal2(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        var stack: [TreeNode] = []
        var p: TreeNode? = root
        
        while p != nil || !stack.isEmpty {
            while p != nil {
                stack.append(p!)
                p = p!.left
            }
            p = stack.popLast()!
            result.append(p!.val)
            p = p!.right
        }
        
        return result
    }
    
    /// 3.栈+辅助节点
    class func inorderTraversal3(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        
        var p: TreeNode? = root
        var tree: [TreeNode] = []
        
        while !tree.isEmpty || p != nil {
            if p != nil {
                tree.append(p!)
                p = p?.left
            } else {
                let node = tree.popLast()!
                result.append(node.val)
                p = node.right
            }
        }
        return result
    }
}
print("中序")
print(Solution2.inorderTraversal(root))
print(Solution2.inorderTraversal2(root))
print(Solution2.inorderTraversal3(root))
/*:
 ### 145. Binary Tree Postorder Traversal
 Given a binary tree, return the postorder traversal of its nodes' values.
 给定一个二叉树，返回它的 后序 遍历。
 ```
 Input: [1,null,2,3]
 1
   \
     2
   /
 3
 Output: [3,2,1]
 ```
 Follow up: Recursive solution is trivial, could you do it iteratively?
 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 */
class Solution3 {
    /// 1. 递归
    class func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        
        result += postorderTraversal(root.left)
        result += postorderTraversal(root.right)
        result.append(root.val)
        return result
    }
    /// 2. 栈+迭代
    class func postorderTraversal2(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        var stack: [TreeNode] = []
        stack.append(root)
        var head: TreeNode? = root
        
//        while !stack.isEmpty {
//            let node = stack.last!
//
//            if (node.left == nil && node.right == nil) ||
//                node.left == head || node.right == head {
//                result.append(node.val)
//                head = node
//            } else {
//                if node.right != nil {
//                    stack.append(node)
//                }
//                if node.left != nil {
//                    stack.append(node)
//                }
//            }
//
//        }
        
        return result
    }
    /// 2. 栈+迭代+辅助节点
    class func postorderTraversal3(_ root: TreeNode?) -> [Int] {
        var result: [Int] = []
        guard let root = root else {
            return result
        }
        
        var p: TreeNode? = root
        var tree: [TreeNode] = []
        
        while !tree.isEmpty || p != nil {
            if p != nil {
                tree.append(p!)
                result.insert(p!.val, at: 0)
                p = p!.right
            } else {
                p = tree.popLast()!.left
            }
        }
        return result
    }
}
print("后序")
print(Solution3.postorderTraversal(root))
print(Solution3.postorderTraversal2(root))
print(Solution3.postorderTraversal3(root))

//: [Next](@next)
